package com.jxb.first;

public class LinkedListCycle {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        listNode1.val = 1;
        ListNode listNode2 = new ListNode();
        listNode2.val = 2;
        ListNode listNode3 = new ListNode();
        listNode3.val = 2;
        ListNode listNode4 = new ListNode();
        listNode4.val = 3;
        listNode4.next = listNode2;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;
        ListNode listNode = linkedListCycle1(listNode1);
        System.out.println(listNode);
    }

    //弗洛伊德算法
    public static boolean linkedListCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode slowPtr = head,fastPtr = head;
        while (fastPtr.next != null && fastPtr.next.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr) {
                return true;
            }
        }
        return false;
    }

    //弗洛伊德算法-给定一个链表，返回链表开始入环的第一个节点
    public static ListNode linkedListCycle1(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slowPtr = head,fastPtr = head;
        boolean isCy = false;
        while (fastPtr.next != null && fastPtr.next.next != null) {
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
            if (slowPtr == fastPtr) {
                isCy = true;
                break;
            }
        }
        if (isCy) {
            slowPtr = head;
            while (slowPtr != fastPtr) {
                fastPtr = fastPtr.next;
                slowPtr = slowPtr.next;
            }
            return slowPtr;//返回环的开始节点
        }
        return null;
    }

}
